networkedlifeq21fandomcom-20200213-history
How does FEDEX or UPS choose the optimal route to deliver packages? by Anil Kumar Gowda Thammaiah, Sunil Golla
A Short Answer Transportation of goods is an important task in today’s society. People need to send packages, documents or other important things from one place to another on a regular basis. We usually rely on courier services to do this job for us. Most customers wish to receive their packages within one to two days, which makes the courier service industry an essential tool for any business. Therefore, the company’s goal is to make sure their customer’s delivery requests succeed their expectations. In order to accomplish this, huge amounts of money is being spent by the courier service daily on fuel, equipment, maintenance of equipment and wages. Time is money, and using the most efficient route to deliver packages can drastically reduce the time it takes to make these deliveries. Even small improvements can lead to huge improvements in absolute terms. The improvements are not only in terms of better mileage, they also help cut fuel usage, decrease carbon emissions, improve asset utilization, and increase customer service. A few notable players in the USA for providing courier services are United Parcel Service, Inc. (UPS), DHL Express, FedEx Corporation, Etc. Let’s assume an average driver makes about 120 deliveries per day. To figure out how many different possible routes that driver could travel, just start multiplying: 120! = 120 \times119\times118.........\times3\times2\times1 = 6.68\times10^{198} This result far exceeds the age of the Earth in nanoseconds. So, how to find the most optimal route among 6.68\times10^{198} combinations that could minimize the total expense by meeting the demands of the customers? This question can be divided into three sub-questions. 1.There might be several delivery centers in a city, so which delivery center is responsible for a particular package? This solution to this question is relatively very simple. Each delivery center can be made responsible for a particular set of zip codes and the package belonging to a particular zip code can be routed to its corresponding delivery center. 2.Now the packages arrived at the delivery center, there might be huge number of packages that several trucks might be required to deliver these packages. So, how to split the routes most effectively between these trucks if more than one truck is being used? The coverage area of the delivery center and number of packages and trucks available for delivery are the two factors that need to be considered to answer this question. A single truck might not be sufficient always to make the deliveries. If two packages need to be delivered to a particular apartment, it is better to have those two packages on the same truck instead of two different trucks. This could be termed as The Vehicle Routing Problem and an optimal solution to this problem would result in providing the improvements discussed earlier. 3.Once the packages are in the truck and if there are a set of addresses where the packages are to be delivered, what is an efficient order to visit them? The truck needs to go through the addresses that have been given and there are different routes that can be taken. If the driver visits a building and delivers a package, then goes around and comes back to the same building but this time for a different package, then this is not an efficient route. This can be termed as The ''Traveling Salesman Problem. '''A Long Answer' The Vehicle Routing Problem The vehicle routing problem (VRP) is a well known combinatorial optimization and integer programming problem. Traditionally, the VRP is defined as a routing problem with a single depot, a set of customers, multiple vehicles and the objective to minimize the total cost while servicing every customer. Each vehicle that services customers starts the travel from the depot and finishes it in the depot as well. The objective of the typical VRP is to find the solution, at first, minimizing the total vehicle number required, and secondly, minimizing the length of the total traveled path. This problem was first formulated by Dantzig and Ramser (1959). The vehicle routing problem typically is described as a graph G=\left(V,E\right) and a set of homogeneous vehicles K=\left\{k_{1},k_{2},k_{3}......,k_{n}\right\} where t is the number of vehicles. The graph G consists of the nodes V=\left\{0,1,2,......,k\right\} where 0 is a depot and V\{0} are k customers that need to be serviced, and edges E={x_{ij}} between each node where i\neq{j}, 0\leq{i}\leq{k} and 0\leq{j}\leq{k} For the set E, the cost matrix C is defined, where c_{ij} is the cost of the edge x_{ij}=\left(i,j\right), and c_{ii}=0 . Usually the VRP is treated as symmetric, where c_{ij}=c_{ji} . In the real world problem, the cost matrix is asymmetric and needs to be calculated from geographic data by using the shortest path algorithms. Moreover, if a vehicle set is not homogeneous, some roads can be forbidden for certain vehicles and allowed for others. The different shortest path can exist for a different vehicle type, so a different matrix needs to be calculated for all the different vehicle types. Various constraints can be added to the VRP. The defined constraints usually refer to real life situations. The most known constraint for the VRP is the capacity constraint. The capacity constraints S_{c}\sqsubseteq{S} are carriage limitations applied to each vehicle. A capacitated vehicle routing problem (CVRP) is usually defined with equal capacities for all vehicles. However, in real life vehicle fleet with different capacities can be used to solve the delivery problem. VRP Formulation The\ objective\ of\ VRP\ is\ to minimize\sum_{i\epsilon{V}}\sum_{j\epsilon{V}}c_{ij}x_{ij} subject\ to\ constraints \sum_{i\epsilon{V}}x_{ij}=1\ \ \ \forall{j\epsilon{V}}\backslash\left\{0\right\}\ \ \ \left(1\right) \sum_{j\epsilon{V}}x_{ij}=1\ \ \ \forall{i\epsilon{V}}\backslash\left\{0\right\}\ \ \ \left(2\right) \sum_{i\epsilon{V}}x_{i0}=K\ \ \ \left(3\right) \sum_{j\epsilon{V}}x_{0j}=K\ \ \ \left(4\right) \sum_{i\notin{S}}\sum_{j\epsilon{S}}x_{ij}\geq{S_{c}}\ \ \ \forall{S}\subseteq{V}\backslash{0},S\neq{0}\ \ \ \left(5\right) x_{ij}\epsilon{\left\{0,1\right\}}\ \ \ \forall{i,j}\epsilon{V}\ \ \ \left(6\right) Constraints (1) and (2) state that exactly one arc enters and exactly one leaves each vertex associated with a customer, respectively. Constraints (3) and (4) say that the number of vehicles leaving the depot is the same as the number entering. Constraints (5) is the capacity cut constraint, which impose that the routes must be connected and that the demand on each route must not exceed the vehicle capacity. Finally, constraints (6) are the integrality constraints. A number of different exact and heuristic methods have been studied to solve the VRP that is known to be NP-hard. Although the exact methods give the optimal solution, their computation time considerably increases with the increasing size of the problem. Various heuristic methods exist for solving problems that are known to be NP-hard. One among them is the Savings algorithm. Savings algorithm was proposed by Clark and Wright (1964). Algorithm starts with the initial solution where all nodes are visited by separate route from depot. The algorithm search and merges two routes by maximizing the saving cost, where cost typically is a distance. Merge is possible, if merged route remains feasible. Savings algorithm Suppose that initially the solution to the VRP consists of using n vehicles and dispatching one vehicle to each one of the n demand points. The total tour length of this solution is, obviously, Total tour length = 2\sum_{j=1}^nx_{0j} If now we use a single vehicle to serve two points, say i and j, on a single trip, the total distance traveled is reduced by the amount s_{ij} = 2x_{0i}+ 2x_{0j}-\leftx_{0j}+x_{ij}\right =x_{0i}+ x_{0j}-x_{ij} The quantity s_{ij} is known as the "Savings" resulting from combining points i and j into a single tour. The larger s_{ij} is, the more desirable it becomes to combine i and j in a single tour. However, i and j cannot be combined if in doing so the resulting tour violates one or more of the constraints of the VRP. The algorithm can be described as follows. Step 1: Calculate the savings s_{ij}=x_{0i}+ x_{0j}-x_{ij} for every pair \left(i,j\right) of demand points. Step 2: Rank the savings s_{ij} and list them in descending order of magnitude. This creates the "Savings list." Process the savings list beginning with the topmost entry in the list (the largest s_{ij} ). Step 3: For the savings s_{ij} under consideration, include link \left(i,j\right) in a route if no route constraints will be violated through the inclusion of \left(i,j\right) in a route, and if: * Either, neither i nor j have already been assigned to a route, in which case a new route is initiated including both i and j. * Or, exactly one of the two points \left(i\ or\ j\right) has already been included in an existing route and that point is not interior to that route (a point is interior to a route if it is not adjacent to the depot in the order of traversal of points), in which case the link \left(i,j\right) is added to that same route. * Or, both i and j have already been included in two different existing routes and neither point is interior to its route, in which case the two routes are merged. Step 4: If the savings list s_{ij} has not been exhausted, return to Step 3, processing the next entry in the list; otherwise, stop: the solution to the VRP consists of the routes created during Step 3. (Any points that have not been assigned to a route during Step 3 must each be served by a vehicle route that begins at the depot D visits the unassigned point and returns to D.) Example – VRP Consider a VRP where the Depot is node 0 and the nine points are the set of nodes that need to be serviced. The distances and savings between each node is provided in the below matrix. Since the distances are symmetric, the savings s_{ij} is computed using the equation: s_{ij}=x_{0i}+ x_{0j}-x_{ij} and shown in the same matrix. The distances are below the diagonal and the savings are shown above the diagonal. For instance: s_{35}=x_{03}+ x_{05}-x_{35}=57+61-71=47 Table 1: The distances (below diagonal) and savings (above diagonal) associated with each node is given in the above table. We assume that the capacity of each vehicle is 23 and apply the third step of the Savings algorithm to the savings list, as shown in Table 1. No constraint other than the maximum capacity one is assumed to exist. Table 2: Lists the quantities of packages that are be delivered at each node. Table 3: The computed savings by merging two nodes arranged in the descending order. The processing of the savings list now proceeds as follows. The largest savings is associated with link (5, 9), so a tour consisting of {0, 5, 9, 0} is created. The second entry in the list is associated with link (8, 9). The initial route is therefore expanded to {0, 5, 9, 8, 0} since the conditions under Step 3 are satisfied by such an expansion. Next is the entry for link (7, 8) and expansion of the route to {0, 5, 9, 8, 7, 0} also turns out to be acceptable. However, expansion to {0, 4, 5, 9, 8, 7, 0}, as suggested by the next entry for link (4, 5), is impossible since such a route would imply a load of 24 units (> 23). Thus, link (4, 5) is rejected. So is link (7,9) as both 7 and 9 are already in the tour; and (6, 9) since 9 is interior to the tour. The appearance of link (3, 4) as the next entry in the savings list leads to formation of another tour {0, 3, 4, 0}. Next, the inclusion of point 6 in the first tour is acceptable and that tour is expanded to {0, 6, 5, 9, 8, 7, 0} with a load of 23 (meaning that this tour cannot be expanded further). Proceeding in the same way, points 2 and then 1 are successively added to the second tour, ending up with the tour {0, 1, 2, 3, 4, 0}, with a load of 19 units. Since all points have been included in a tour, that also means the completion of our procedure. The two tours are shown in Figure 1 and their combined length (total distance traveled) is 397 units. Figure 1: Solution to the VRP using Savings algorithm, when vehicle capacity is 23 units. The Travelling Salesman Problem The travelling salesman problem (TSP) asks the following question: Given a list of nodes and the distances between each pair of nodes, what is the shortest possible route that visits each node exactly once and returns to the origin node? It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science. TSP Formulation TSP can be formulated as an integer linear program. x_{ij}=\begin{cases}1 & {the\ path\ goes\ from\ node\ i\ to\ j}\\0 & {otherwise}\end{cases} For i=0,1,2,......,n . Let c_{ij} be the distance from node i to node j. Then TSP can be written as the following integer linear programming problem: min\sum_{i=0}^n\sum_{j\neq{i},j=0}^nc_{ij}x_{ij} subject to the constraints \sum_{i=0,i\neq{j}}^nx_{ij}=1\ \ \ \ \ \ j=0,1,......,n\ \ \ \left(7\right) \sum_{j=0,j\neq{i}}^nx_{ij}=1\ \ \ \ \ \ i=0,1,......,n\ \ \ \left(8\right) 0\leq{x_{ij}}\leq{1}\ \ \ \ \ \ i,j=0,1,......,n\ \ \ \left(9\right) Constraint (7) requires that each node be arrived from exactly one other node, and constraint (8) requires that from each node there is a departure to exactly one other node. The last constraint (9) enforces that there is only a single tour covering all nodes, and not two or more disjointed tours that only collectively cover all nodes. Although optimal algorithms exist for solving the TSP, like the IP formulation, industrial engineers have realized that it is computationally infeasible to obtain the optimal solution to TSP. And it has been proved that for large-size TSP, it is almost impossible to generate an optimal solution within a reasonable amount of time. Heuristics, instead of optimal algorithms, are extensively used to solved such problems. People conceived many heuristic algorithms to get near optimal solutions. Among them, there are greedy, 2-opt, 3-opt, simulated annealing, genetic algorithms, neural network approach, etc. But their efficiencies vary from case to case, from size to size. One such heuristic with a greedy approach is Nearest Neighbor Algorithm. Nearest Neighbor Algorithm The nearest neighbor algorithm was one of the first algorithms used to determine a solution to the TSP. It is a greedy algorithm for finding a sub-optimal solution to the TSP. The algorithm can be described as follows: Step 1: '''Start at the depot '''Step 2: '''Next address will be the closest as yet unvisited one (if there are two or more at the same closest distance, just pick any one of them) '''Step 3: '''Visit the node '''Step 4: '''Repeat 2 and 3 until no more unvisited nodes '''Step 5: '''End at the depot '''Example - TSP Consider a fully connected graph G where the depot is at node A and B, C, D and E are the set of nodes that need to be visited exactly once. The Nearest neighbor algorithm can be used to find the sub-optimal route as described below. Figure 2: A graph with 5 nodes where node A is the depot and B, C, D and E are the set of nodes that need to be visited exactly once. The route must start at node A as it is the depot. Among the nodes B, C D and E the nearest node is D with a cost of 185. The node D is marked as visited. Among the remaining unvisited nodes E, C and B the nearest unvisited node from D is E. Node E is marked as visited and the next node that need to be visited is C with a cost 165. The node B will be visited next as it is the only unvisited node remaining and the final route will be ADECBA. The total cost of the route would be: AD+DE+EC+CB+BA=185+302+165+305+500=1457 Figure 3: This graph represents the route ADECBA calculated using the Nearest neighbor algorithm. The total cost of the route is 1457. Conclusion Until recently, UPS used a software tool that gave drivers a general route to follow but allowed wide latitude for human judgment along the way. Now, it is using a route optimization tool called ORION – On Road Integrated Optimization and Navigation which aims to deliver the best answer to the travelling salesman problem, the classic computational conundrum that shows just how hard it is to find the shortest distance among a series of points on a map. The size of the numbers involved in solving the TSP makes it hard to compute solutions using exact algorithms. Hence, ORION depends on heuristics, the field of math and computer science devoted to finding answers that are good enough, and that get better based on past experience. Of course, finding the shortest distance is only one of many variables in play for UPS. Promised delivery times, different types of customers and the types of packages being delivered and picked up are just a few of the additional factors ORION must take into consideration. By the end of 2013, ORION was deployed on 10000 routes and is expected to be deployed on all 55000 routes by 2017. With 10,000 routes optimized with ORION, UPS saves more than 1.5 million gallons of fuel and reduces carbon dioxide emissions by 14,000 metric tons. This game changing operations research project of UPS has won the prestigious INFORMS Franz Edelman Award for Achievement in Operations Research and the Management Sciences. Once deployed across all the routes, ORION is expected to result in an annual savings of 10 million gallons of fuel, a reduction of 100,000 metric tons in CO2 emissions, and an estimated $300 to $400 million in savings and cost avoidance. References * The Astronomical Math Behind UPS’ New Tool to Deliver Packages Faster. (n.d.). Retrieved from http://www.wired.com/2013/06/ups-astronomical-math/ * Section 6-4-12. (n.d.). Retrieved from http://web.mit.edu/urban_or_book/www/book/chapter6/6.4.12.html * Philip J. Owens -- ACC Home Page. (n.d.). Retrieved from http://www.austincc.edu/powens/ Topics/HTML/06-5/06-5.htm * UPS 1st Quarter 2016 Financial Tables. (n.d.). Retrieved from https://www.pressroom.ups.com/pressroom/ContentDetailsViewer.page?ConceptType=Factsheets * UPS Wins 2016 INFORMS Franz Edelman Award For Changing The Future Of Package Delivery. (n.d.). Retrieved from https://pressroom.ups.com/pressroom/ContentDetailsViewer.page?ConceptType=PressReleases * Travelling salesman problem. (n.d.). Retrieved from https://en.wikipedia.org/wiki/Travelling_salesman_problem * Vehicle routing problem. (n.d.). Retrieved from https://en.wikipedia.org/wiki/Vehicle_routing_problem * Choosing a Route Planning System. (n.d.). Retrieved from http://www.inboundlogistics.com/cms/article/choosing-a-route-planning-system/ * Ropke, S. (2005). Heuristic and exact algorithms for vehicle routing problems. Unpublished PhD thesis, Computer Science Department, University of Copenhagen.